package code.ws_common_scene.astar
{
	import flash.geom.Point;
	import code.ws_common_scene.map.MapData;
	
	/**
	 *  Astar寻路机制
	 * @author qiangchen
	 * 
	 */	
	public class AStar
	{	
		/** 对角耗费 */
		private const COST_DIAGONAL:int = 14;
		/** 直线耗费 */
		private const COST_STRAIGHT:int = 10;
		private const NOTE_ID:int = 0;
		private const NOTE_OPEN:int = 1;
		private const NOTE_CLOSED:int = 2;
		
		/** 地图网络格数据 */
		private var m_mapTileModel:MapData;
		/** 最大尝试次数 */
		private var m_maxTry:int; 		
		/** 开放列表计数器 */
		private var m_openCount:int; 
		/** 开放列表编号 */
		private var m_openId:int; 
		private var m_openList:Array;
		private var m_xList:Array;
		private var m_yList:Array;
		private var m_pathScoreList:Array;
		private var m_movementCostList:Array;
		private var m_fatherList:Array;
		private var m_noteMap:Array;
		
		/**
		 * 构造函数 
		 * @param p_maxTry 最大尝试次数
		 * 
		 */		
		public function AStar(p_maxTry:int = 1000)
		{
			this.m_maxTry = p_maxTry;
		}
		
		/**
		 * 寻路 
		 * @param p_startX 起始点x轴
		 * @param p_startY 起始点y轴
		 * @param p_endX  终点x轴
		 * @param p_endY 终点y轴
		 * @return 
		 * 
		 */		
		public function find(p_startX:int, p_startY:int, p_endX:int, p_endY:int, p_mapTileModel:MapData) : Array
		{
			this.m_mapTileModel = p_mapTileModel;
			
			
			if ( this.m_mapTileModel.isBlock(p_endX, p_endY) )
			{
				var nearlyPt:Point = this.resetTarget(p_startX,p_startY,p_endX,p_endY);
				if(nearlyPt == null)
				{
					return null;
				}
				p_endX = nearlyPt.x;
				p_endY = nearlyPt.y;
			}
			
			var try_count:uint = 0;
			var cur_id:int = 0;
			var p_x:int = 0;
			var p_y:int = 0;
			var cost:int = 0;
			var score:int = 0;
			var node_id:int = 0;
			var _arounds:Array = null;
			
			this.initLists();
			this.m_openCount = 0;
			this.m_openId = -1;
			this.openNote(p_startX, p_startY, 0, 0, 0);
			
			while(this.m_openCount > 0){
				if (++try_count >= this.m_maxTry)
				{
					this.destroyLists();
					return null;
				}
				
				cur_id = this.m_openList[0];
				this.closeNote(cur_id);
				p_x = this.m_xList[cur_id];
				p_y = this.m_yList[cur_id];
				
				if (p_x == p_endX && p_y == p_endY)
				{
					return this.getPath(p_startX, p_startY, cur_id);
				}
				_arounds = getArounds(p_x,p_y);
				for each(var _temps:Array in _arounds)
				{
					cost = this.m_movementCostList[cur_id] + (_temps[0] != p_x && _temps[1] == p_y ? (COST_STRAIGHT) : (COST_DIAGONAL));
					score = cost + (Math.abs(p_endX - _temps[0]) + Math.abs(p_endY - _temps[1])) * COST_STRAIGHT;
					if (this.isOpen(_temps[0], _temps[1]))
					{
						node_id = this.m_noteMap[_temps[1]][_temps[0]][NOTE_ID];
						if (cost < this.m_movementCostList[node_id])
						{
							this.m_movementCostList[node_id] = cost;
							this.m_pathScoreList[node_id] = score;
							this.m_fatherList[node_id] = cur_id;
							this.aheadNote(this.getIndex(node_id));
						}
						continue;
					}
					this.openNote(_temps[0], _temps[1], score, cost, cur_id);
				}
			}
			this.destroyLists();
			return null;
		}
		
		private function getArounds(p_x:int, p_y:int) : Array
		{
			var _cur_px:int = 0;
			var _cur_py:int = 0;
			var _arounds:Array = [];
			_cur_px = p_x + 1;
			_cur_py = p_y;
			var isBlock:Boolean = this.m_mapTileModel.isBlock(_cur_px, _cur_py);
			
			if (!isBlock && !this.isClosed(_cur_px, _cur_py))
			{
				_arounds.push([_cur_px, _cur_py]);
			}
			_cur_px = p_x;
			_cur_py = p_y + 1;
			isBlock = this.m_mapTileModel.isBlock(_cur_px, _cur_py);
			
			if (!isBlock && !this.isClosed(_cur_px, _cur_py))
			{
				_arounds.push([_cur_px, _cur_py]);
			}
			_cur_px = p_x - 1;
			_cur_py = p_y;
			isBlock = this.m_mapTileModel.isBlock(_cur_px, _cur_py);
			
			if (!isBlock && !this.isClosed(_cur_px, _cur_py))
			{
				_arounds.push([_cur_px, _cur_py]);
			}
			_cur_px = p_x;
			_cur_py = p_y - 1;
			isBlock = this.m_mapTileModel.isBlock(_cur_px, _cur_py);
			
			if (!isBlock && !this.isClosed(_cur_px, _cur_py))
			{
				_arounds.push([_cur_px, _cur_py]);
			}
			_cur_px = p_x + 1;
			_cur_py = p_y + 1;
			isBlock = this.m_mapTileModel.isBlock(_cur_px, _cur_py);
			
			if (!isBlock && !this.isClosed(_cur_px, _cur_py))
			{
				_arounds.push([_cur_px, _cur_py]);
			}
			_cur_px = p_x - 1;
			_cur_py = p_y + 1;
			isBlock = this.m_mapTileModel.isBlock(_cur_px, _cur_py);
			
			if (!isBlock && !this.isClosed(_cur_px, _cur_py))
			{
				_arounds.push([_cur_px, _cur_py]);
			}
			_cur_px = p_x - 1;
			_cur_py = p_y - 1;
			isBlock = this.m_mapTileModel.isBlock(_cur_px, _cur_py);
			
			if (!isBlock && !this.isClosed(_cur_px, _cur_py))
			{
				_arounds.push([_cur_px, _cur_py]);
			}
			_cur_px = p_x + 1;
			_cur_py = p_y - 1;
			isBlock = this.m_mapTileModel.isBlock(_cur_px, _cur_py);
			
			if (!isBlock && !this.isClosed(_cur_px, _cur_py))
			{
				_arounds.push([_cur_px, _cur_py]);
			}
			return _arounds;
		}
		
		private function getPath(p_startX:int, p_startY:int, p_id:int) : Array
		{
			var _path:Array = [];
			var p_x:int = this.m_xList[p_id];
			var p_y:int = this.m_yList[p_id];
			
			while(p_x != p_startX || p_y != p_startY)
			{
				_path.unshift([p_x, p_y]);
				p_id = this.m_fatherList[p_id];
				p_x = this.m_xList[p_id];
				p_y = this.m_yList[p_id];
			}
			_path.unshift([p_startX, p_startY]);
			
			this.destroyLists();
			return _path;
		}
		
		private function openNote(p_x:int, p_y:int, p_score:int, p_cost:int, p_fatherId:int) : void
		{
			this.m_openCount++;
			this.m_openId++;
			
			if (this.m_noteMap[p_y] == null)
			{
				this.m_noteMap[p_y] = [];
			}
			this.m_noteMap[p_y][p_x] = [];
			this.m_noteMap[p_y][p_x][NOTE_OPEN] = true;
			this.m_noteMap[p_y][p_x][NOTE_ID] = this.m_openId;
			this.m_xList.push(p_x);
			this.m_yList.push(p_y);
			this.m_pathScoreList.push(p_score);
			this.m_movementCostList.push(p_cost);
			this.m_fatherList.push(p_fatherId);
			this.m_openList.push(this.m_openId);
			this.aheadNote(this.m_openCount);
		}
		
		private function closeNote(p_id:int) : void
		{
			this.m_openCount--;
			
			var p_x:int = this.m_xList[p_id];
			var p_y:int = this.m_yList[p_id];
			this.m_noteMap[p_y][p_x][NOTE_OPEN] = false;
			this.m_noteMap[p_y][p_x][NOTE_CLOSED] = true;
			if (this.m_openCount <= 0)
			{
				this.m_openCount = 0;
				this.m_openList = [];
				return;
			}
			this.m_openList[0] = this.m_openList.pop();
			this.backNote();
		}
		
		private function backNote() : void
		{
			var _open_id:int = 0;
			var _cur_id:int = 1;
			while (true)
			{
				_open_id = _cur_id;
				if (2 * _open_id <= this.m_openCount)
				{
					if (this.getScore(_cur_id) > this.getScore((2 * _open_id)))
					{
						_cur_id = 2 * _open_id;
					}
					
					if ((2 * _open_id + 1) <= this.m_openCount)
					{
						if (this.getScore(_cur_id) > this.getScore((2 * _open_id + 1)))
						{
							_cur_id = 2 * _open_id + 1;
						}
					}
				}
				if (_open_id == _cur_id)
				{
					break;
				}
				var _temp_id:int = this.m_openList[_open_id - 1];
				this.m_openList[_open_id - 1] = this.m_openList[_cur_id - 1];
				this.m_openList[_cur_id - 1] = _temp_id;
			}
		}
		
		private function aheadNote(p_index:int) : void
		{
			var ahead:int = 0;
			while (p_index > 1)
			{
				ahead = Math.floor(p_index / 2);
				if (this.getScore(p_index) < this.getScore(ahead))
				{
					var openId:int = this.m_openList[p_index-1];
					this.m_openList[p_index - 1] = this.m_openList[ahead-1];
					this.m_openList[ahead-1] = openId;
					p_index = ahead;
					continue;
				}
				break;
			}
		}
		
		private function getScore(p_index:int) : int
		{
			return this.m_pathScoreList[this.m_openList[p_index-1]];
		}
		
		/**
		 * 初始化测试数据组 
		 * 
		 */		
		private function initLists() : void
		{
			this.m_openList = [];
			this.m_xList = [];
			this.m_yList = [];
			this.m_pathScoreList = [];
			this.m_movementCostList = [];
			this.m_fatherList = [];
			this.m_noteMap = [];
		}
		
		/**
		 * 销毁存储的临时数据 
		 * 
		 */		
		private function destroyLists() : void
		{
			this.m_openList.length = 0;
			this.m_openList = null;
			
			this.m_xList.length = 0;
			this.m_xList = null;
			
			this.m_yList.length = 0;
			this.m_yList = null;
			
			this.m_pathScoreList.length = 0;
			this.m_pathScoreList = null;
			
			this.m_movementCostList.length = 0;
			this.m_movementCostList = null;
			
			this.m_fatherList.length = 0;
			this.m_fatherList = null;
			
			this.m_noteMap.length = 0;
			this.m_noteMap = null;
		}
		
		/**
		 * 当目标点为不可行走点时，寻找最近的可行走点 
		 * @param p_startX
		 * @param p_startY
		 * @param p_endX
		 * @param p_endY
		 * @return 
		 * 
		 */		
		private function resetTarget(p_startX:int, p_startY:int, p_endX:int, p_endY:int) : Point
		{
			var try_count:uint = 0;
			while(this.m_mapTileModel.isBlock(p_endX, p_endY))
			{
				if (++try_count >= this.m_maxTry)
				{
					return null;
				}
				
				if(p_endX > p_startX)
				{
					p_endX--;
				}
				else if(p_endX < p_startX)
				{
					p_endX++;
				}
				
				if(p_endY > p_startY)
				{
					p_endY--;
				}
				else if(p_endY < p_startY)
				{
					p_endY++;
				}
			}
			return new Point(p_endX, p_endY);
		}
		
		private function getIndex(p_id:int) : int
		{
			var _open_id:int = 0;
			var _index:int = 1;
			for each (_open_id in this.m_openList)
			{
				
				if (_open_id == p_id)
				{
					return _index;
				}
				_index++;
			}
			return -1;
		}
		
		/**
		 * 开放列表 
		 * @param p_x
		 * @param p_y
		 * @return 
		 * 
		 */		
		private function isOpen(p_x:int, p_y:int) : Boolean
		{
			if (this.m_noteMap[p_y] == null)
			{
				return false;
			}
			if (this.m_noteMap[p_y][p_x] == null)
			{
				return false;
			}
			return this.m_noteMap[p_y][p_x][NOTE_OPEN];
		}
		
		
		/**
		 * 关闭列表 
		 * @param p_x
		 * @param p_y
		 * @return 
		 * 
		 */		
		private function isClosed(p_x:int, p_y:int) : Boolean
		{
			if (this.m_noteMap[p_y] == null)
			{
				return false;
			}
			if (this.m_noteMap[p_y][p_x] == null)
			{
				return false;
			}
			return this.m_noteMap[p_y][p_x][NOTE_CLOSED];
		}
		
		/**
		 * 释放 
		 * 
		 */		
		public function dispose():void
		{
			m_mapTileModel = null;
			
			m_openList.length = 0;
			m_openList = null;
			
			m_xList.length = m_yList.length = 0;
			m_xList = null;
			m_yList = null;
			
			m_pathScoreList.length = 0;
			m_pathScoreList = null;
			
			m_movementCostList.length = 0;
			m_movementCostList = null;
			
			m_fatherList.length = 0;
			m_fatherList = null;
			
			m_noteMap.length = 0;
			m_noteMap = null;
		}
	}
}